package com.chapter16;

import java.util.ArrayList;
import java.util.List;

public class PowerSet {
	
	
	
	public void getPowerSet(int[] A,List<Integer> l,int index){
		System.out.println(l);
		if(index==A.length){
			return;
		}
		for(int i=index;i<A.length;i++){
			l.add(A[i]);
			getPowerSet(A,l,i+1);
			l.remove(l.size()-1);
		}
	}
	
	public void testgetPowerSet(){
		int[] A={1,2,3};
		List<Integer> l=new ArrayList<Integer>();
		getPowerSet(A,l,0);
	}
	
	public List<ArrayList<Integer>> getPowerSetSizeK(List<ArrayList<Integer>> l,int n, int k, int c){
		if(c==k+1)
			return l;
		
		if(l.isEmpty()){
			int endIndex=n-k+c;
			for(int i=0;i<endIndex;i++){
				ArrayList<Integer> cur=new ArrayList<Integer>();
				cur.add(i);
				l.add(cur);
			}
			return getPowerSetSizeK(l,n,k,c+1);
		}
		
		int sizz=l.size();
		for(int i=0;i<sizz;i++){
			int endIndex=n-k+c;
			List<Integer> cur=l.remove(0);
			int lastElementofCur=cur.get(cur.size()-1);
			for(int j=lastElementofCur+1;j<endIndex;j++){
				ArrayList<Integer> newList=new ArrayList<Integer>();
				newList.addAll(cur);
				newList.add(j);
				l.add(newList);
			}
		}
		return getPowerSetSizeK(l,n,k,c+1);
		
	}
	
	public void testgetPowerSetSizeK(){
		int n=6;
		int k=5;
		List<ArrayList<Integer>>l=new ArrayList<ArrayList<Integer>>();
		System.out.println(getPowerSetSizeK(l,n,k,1));
	}
}
